#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
/*
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 
注意：解集不能包含重复的组合。 
解题思路：
该题与之前的组合总和不同，改题目给出的集合中包含相同的元素，所以在path结果中能够含有相同的元素如：1，1，2
但是结果集中不能出现相同的组合，若目标集合：1，1，2；
第一次取1，向下遍历时第二次可以取1，2；若第一次取下标为1的元素1，则第二次能取2；这样就会使得与第一次取下标为0时候的1情况重复
所以我们要进行去重操作,去重要在什么情况下进行去重呢，当树形结构向下递归时遇到与path结果集中相同的元素是不需要进行去重的，
只有在树形结构的同一层中，一个节点与它的左兄弟取到相同元素的话就要将该节点进行去重操作，那么应该如何区分是递归时候取到相同的元素
还是进行回溯之后取到相同的元素呢，可以设置一个used数组来标记取过的元素,每次递归完之后将used回溯，这样遍历树层的时候取到相同元素
前面的元素一定是used中没有标记过的元素
*/

vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> candidates,int target,int sum,int index,vector<int> used)
{
    //递归终止条件
    if(sum>target)
        return;
    else if(sum==target)
    {
        result.push_back(path);
        return;
    }   
    for(int i=index;i<candidates.size();i++)
    {
        //进行树层去重,取到的数等于前一个树，并且前一个数的状态是未取，不然就是递归
        if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0)
            continue;
        sum+=candidates[i];
        path.push_back(candidates[i]);
        used[i] = 1;
        backtracking(candidates,target,sum,i+1,used);
        //回溯
        sum-=candidates[i];
        path.pop_back();
        used[i]=0;
    }
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    //先进行排序
    sort(candidates.begin(),candidates.end());
    vector<int> used(candidates.size(),0);
    backtracking(candidates,target,0,0,used);
    return result;
}
int main()
{
    cout<<"enter target:"<<endl;
    int target;
    cin>>target;
    cout<<"enter number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter candidates:"<<endl;
    vector<int> candidates(number);
    for(int i=0;i<number;i++)
    {
        cin>>candidates[i];
    }
    vector<vector<int>> result = combinationSum2(candidates,target);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}